/*
 * sort.c
 *
 *  Created on: 2010-6-12
 *      Author: Anders
 */

#include <stdio.h>

#define MAX_ARRAY_SIZE 100

#ifdef DEBUG_PRINT
#define PRINT  printf
#else
#define PRINT(...) do {} while (0)
#endif

void usage()
{
	printf("[Usage] sort (insertion | merge | merge_insertion | quick)\n");
}

void
insertion_sort(int array[], int length)
{
	int i, j, key;
	
	for (j = 1; j < length; j++) {
		i = j - 1;
		key = array[j];
		while (i >= 0 && array[i] > key) {
			array[i + 1] = array[i];
			i--;
		}
		array[i + 1] = key;
	}
}

void
merge(int array[], int p, int q, int r, int size)
{
	int n1, n2;
	int left[MAX_ARRAY_SIZE], right[MAX_ARRAY_SIZE];
	int i, j, k;
	
	p = p * size;
	q = q * size + size -1;
	r = r * size + size -1;

	n1 = q - p + 1;
	n2 = r - q;
	
	/* devide */
	PRINT("(p:%4d, q:%4d, r:%4d)\n", p, q, r);
	for ( i = 0; i < n1; ++i) {
		left[i] = array[p + i];
	}
	for ( i = 0; i < n2; ++i) {
		right[i] = array[q + 1 + i];
	}
	/* conquer */
	j = k = 0;
	for ( i = p; i <= r; i++) {
		if (j == n1) { /* l array is empty */
			while ((k < n2) && (i <= r)) {
				array[i++] = right[k++];
			}
			break;
		}
		if (k == n2) { /* r array is empty */
			while ((j < n1) && (i <= r)) {
				array[i++] = left[j++];
			}
			break;
		}
		if (left[j] < right[k]) {
			array[i] = left[j++];
		} else {
			array[i] = right[k++];
		}
	}
}

void
merge_sort(int array[], int p, int r, int size)
{
	int q;

	if (r > p) {
		q = (p + r) / 2;
		merge_sort(array, p, q, size);
		merge_sort(array, q + 1, r, size);
		merge(array, p, q, r, size);
	}
}

void
merge_insertion_sort(int array[], int n, int k)
{
	int i, block;

	block = n / k;
	// use insertion method to sort every block
	for (i = 0; i < block; ++i) {
		insertion_sort(array + i * k, k);
	}
	// merge blocks
	merge_sort(array, 0, block - 1, k);
	// specical treatment to rest elements
	if ( n % k != 0) {
		insertion_sort(array + block * k , n % k);
		merge(array, 0, k * block - 1, n - 1, 1);
	}
}

int partition(int array[], int p, int r)
{
	int i, j, key, temp;
	
	i = p - 1;
	key = array[i];

	PRINT("[partition] %d, %d\n", p, r);

	for (j = p; j < r; j++) {
		if ( array[j] < key) {
			if(++i == j) {
				continue;
			}
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}

	array[p - 1] = array[i];	
	array[i] = key;

	PRINT("pivot: %d\n", i + 1);

	return (i + 1);
}

void quick_sort(int array[], int p, int r)
{
	int q;

	if (p < r) {
		q = partition(array, p, r);
		quick_sort(array, p, q - 1);
		quick_sort(array, q + 1, r);
	}
	return;
}

int
main(int argc, char **argv)
{
	int array[MAX_ARRAY_SIZE] = {20, 4, 23, 3, 1, 2, 5, 19, 18, 10, 
	                             16, 17, 15, 7, 9, 8, 22, 21, 6, 11, 
	                             12, 13, 14};
	int i, n = 23, k = 4;

#if 0	
	n = MAX_ARRAY_SIZE;
#endif
	if (argc != 2) {
		usage();
		return;
	}	
	// print result
	PRINT("Before Array: ");
	for (i = 0; i < n; i++) {
		PRINT("%d, ", array[i]);
	}
	PRINT("\n");

	if (strcmp(argv[1], "insertion") == 0) {
		insertion_sort(array, n);	
	} else if (strcmp(argv[1], "merge") == 0) {
		merge_sort(array, 0, n - 1, 1);
	}  else if (strcmp(argv[1], "merge_insertion") == 0) {
		merge_insertion_sort(array, n, k);
	}  else if (strcmp(argv[1], "quick") == 0) {
		quick_sort(array, 1, n);
	} else {
		usage();
		return;
	}

	// print result
	PRINT("After  Array: ");
	for (i = 0; i < n; i++) {
		PRINT("%d, ", array[i]);
	}
	PRINT("\n");
}


